//  652. 寻找重复的子树

/* 
    如果两颗树具有相同的结构和节点值，则他们是重复的
*/
function TreeNode(val, left, right) {
	this.val = val === undefined ? 0 : val
	this.left = left === undefined ? null : left
	this.right = right === undefined ? null : right
}
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
/* 使用序列化进行唯一表示 */
var findDuplicateSubtrees = function (root) {
	const seen = new Map()
	const repeat = new Set()
	const dfs = (node) => {
		if (!node) return ''
		let sb = ''
		sb += node.val
		sb += '('
		sb += dfs(node.left)
		sb += ')('
		sb += dfs(node.right)
		sb += ')'
		if (seen.has(sb)) {
			repeat.add(seen.get(sb))
		} else {
			seen.set(sb, node)
		}
		return sb
	}
	dfs(root)
	return [...repeat]
}
/* 
    使用三元自进行唯一表示
    我们可以使用一个三元组直接b表示一课子树，即(x,l,r) 他们分别表示
    x:根节点
    l:左子树的序号为l
    r:右子树的序号为r
    序号: 每当我们发现一颗新的子树就给这颗子树一个序号，用来表示其结构那么两颗树是
    重复的，当且仅当他们对应的三元组完全相同
*/
var findDuplicateSubtrees = function (root) {
	const seen = new Map()
	const repeat = new Map()
	let idx = 0
	const dfs = (node) => {
		if (!node) return 0
		const tri = [node.val, dfs(node.left), dfs(node.right)]
		const hash = tri.join('')
		if (seen.has(hash)) {
			const pari = seen.get(hash)
			repeat.add(pari[0])
			return pari[1]
		} else {
			seen.set(hash, [node, ++idx])
			return idx
		}
	}
	dfs(node)
	return [...repeat]
}
